'''
https://leetcode.cn/problems/two-city-scheduling/description/
'''

from typing import List
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        m = len(costs)
        n = m // 2
        costs.sort(key=lambda x: abs(x[0] - x[1]), reverse=True)
        i = 0
        a, b = 0, 0
        total = 0
        while a < n and b < n:
            if costs[i][0] <= costs[i][1]:
                total += costs[i][0]
                a += 1
            else:
                total += costs[i][1]
                b += 1
            i += 1
        while a < n:
            total += costs[i][0]
            a += 1
            i += 1
        while b < n:
            total += costs[i][1]
            b += 1
            i += 1
        return total

    def twoCitySchedCost2(self, costs: List[List[int]]) -> int:
        costs.sort(key= lambda x: x[0] - x[1])
        n = len(costs) // 2
        total = 0
        for i in range(n):
            total += costs[i][0] + costs[i+n][1]
        return total

costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
print(Solution().twoCitySchedCost(costs))